import java.util.*;

class TreeNode{
/*    public char val;*/
    public int val;
    public TreeNode left;
    public TreeNode right;
/*    public TreeNode(char val){*/
    public TreeNode(int val){
        this.val = val;
    }
}

public class Test {
    static int i = 0;
    public static TreeNode createTree(String str){
        TreeNode root = null;
        if(str.charAt(i) != '#'){
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        }else{
            i++;
        }
        return root;
    }
    public static void inorderPrint(TreeNode root){
        if(root == null){
            return;
        }
        inorderPrint(root.left);
        System.out.print(root.val + " ");
        inorderPrint(root.right);
    }
    //-------------------------------------------------
    //判断是否是平衡的树
    public static int getHeight(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);
        return Math.max(leftH,rightH) + 1;
    }
    public static boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        if(Math.abs(getHeight(root.left) - getHeight(root.right)) > 1){//当前节点得先是平衡的
            return false;
        }//这条如果能过了就说明当前节点是平衡的
        return isBalanced(root.left) && isBalanced(root.right);
    }
    //----------------------------------------
    //判断是不是对称树
    public static boolean isSymmetricChild(TreeNode left,TreeNode right){
        if((left == null & right != null) ||left != null & right == null){
            return false;
        }
        //左右两个节点要么都空要么都非空了（结构一致）
        if(left == null && right == null){
            return true;
        }
        if(left.val != right.val){
            return false;
        }
        return isSymmetricChild(left.left,right.right) && isSymmetricChild(left.right,right.left);
    }
    public static boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return isSymmetricChild(root.left,root.right);
    }
    //-------------------------------------------------
    //层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> listToatal = new LinkedList<>();

        Queue<TreeNode> queue = new LinkedList<>();
        if(root == null){
            return listToatal;
        }
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new LinkedList<>();
            while(size > 0){
                TreeNode cur = queue.poll();
                if(cur.left != null){
                    queue.offer(cur.left);
                }
                if(cur.right != null){
                    queue.offer(cur.right);
                }
                list.add(cur.val);
                size--;
            }
            listToatal.add(list);
        }
        return listToatal;
    }
    //-----------------------------------------------------
    //寻找两个节点的最近祖先节点
    private boolean getPath(TreeNode root,TreeNode toFind,Stack<TreeNode> stack){
        if(root == null){
            return false;
        }
        stack.push(root);
        if(root == toFind){
            return true;
        }
        boolean ret1 =getPath(root.left,toFind,stack);
        if(ret1 == true){
            return true;
        }
        boolean ret2 =getPath(root.right,toFind,stack);
        if(ret2 == true){
            return true;
        }
        stack.pop();
        return false;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        getPath(root,p,stack1);
        getPath(root,q,stack2);
        int s1L = stack1.size();
        int s2L = stack2.size();
        if(s1L == s2L){
            while(stack1.peek() != stack2.peek()){
                stack1.pop();
                stack2.pop();
            }
            return stack1.pop();
        }else if(s1L > s2L){
            int diffVal = s1L - s2L;
            while(diffVal > 0){
                stack1.pop();
                diffVal--;
            }
        }else{
            int diffVal = s2L - s1L;
            while(diffVal > 0){
                stack2.pop();
                diffVal--;
            }
        }
        while(stack1.peek() != stack2.peek()){
            stack1.pop();
            stack2.pop();
        }
        return stack1.pop();
    }
    //---------------------------------------------------
    //根据前序遍历和中序遍历构建二叉树
/*    int preIndex;
    public TreeNode buildTreeChild(int[] preorder, int[] inorder,int inBegin, int inEnd){
        if(inBegin > inEnd){
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIndex]);
        int rootIndex = findValIndex(inorder,inBegin,inEnd,preorder[preIndex]);
        preIndex++;
        root.left = buildTreeChild(preorder,inorder,inBegin,rootIndex - 1);
        root.right = buildTreeChild(preorder,inorder,rootIndex + 1,inEnd);
        return root;
    }
    public int findValIndex(int[] inorder,int inBegin, int inEnd,int preorderVal){
        for (int j = inBegin; j <= inEnd; j++) {
            if(inorder[j] == preorderVal){
                return j;
            }
        }
        return -1;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int inBegin = 0;
        int inEnd = inorder.length - 1;
        TreeNode root;
        root = buildTreeChild(preorder,inorder,inBegin,inEnd);
        return root;
    }*/
    //---------------------------------------------------
    //根据中序和后序建立树
    int postIndex;

    public TreeNode buildTreeChildBack(int[] inorder, int[] postorder,int inBegin, int inEnd){
        if(inBegin > inEnd){
            return null;
        }
        TreeNode root = new TreeNode(postorder[postIndex]);
        int rootIndex = findValIndex(inorder,inBegin,inEnd,postorder[postIndex]);
        postIndex--;
        root.right = buildTreeChildBack(inorder,postorder,rootIndex + 1,inEnd);//后序遍历先创建的是右树
        root.left = buildTreeChildBack(inorder,postorder,inBegin,rootIndex - 1);
        return root;
    }
    public int findValIndex(int[] inorder,int inBegin, int inEnd,int postorderVal){
        for (int j = inBegin; j <= inEnd; j++) {
            if(inorder[j] == postorderVal){
                return j;
            }
        }
        return -1;
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex = postorder.length - 1;
        int inBegin = 0;
        int inEnd = inorder.length - 1;
        TreeNode root;
        root = buildTreeChildBack(inorder,postorder,inBegin,inEnd);
        return root;
    }

    //---------------------------------------------------
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            TreeNode root = createTree(str);
            inorderPrint(root);
            System.out.println(isBalanced(root));
        }

    }
}